# sourcee:https://leetcode.cn/problems/trapping-rain-water/ 栈 双指针 二刷
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = []
        i = 0
        for j, v in enumerate(height):
            if not stack:
                stack.append(v)
                continue
            if stack[-1] >= v:
                stack.append(v)
            else:
                res = []
                mx = stack[0]
                while stack and stack[-1] < v:
                    res.append(stack.pop())
                if stack:
                    mx = v
                for r in res:
                    ans += (mx - r)
                    if stack:
                        stack.append(mx)
                stack.append(v)
        return ans